home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / stdlib / RCS / memInt.h,v < prev    next >
Encoding:
Text File  |  1991-12-03  |  15.6 KB  |  524 lines
  1. head     1.6;
  2. branch   ;
  3. access   ;
  4. symbols  sprited:1.6.1;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.6
  10. date     90.10.11.22.12.06;  author kupfer;  state Exp;
  11. branches 1.6.1.1;
  12. next     1.5;
  13.  
  14. 1.5
  15. date     89.08.13.16.27.12;  author mgbaker;  state Exp;
  16. branches ;
  17. next     1.4;
  18.  
  19. 1.4
  20. date     89.01.30.15.38.46;  author brent;  state Exp;
  21. branches ;
  22. next     1.3;
  23.  
  24. 1.3
  25. date     88.08.20.21.08.50;  author ouster;  state Exp;
  26. branches ;
  27. next     1.2;
  28.  
  29. 1.2
  30. date     88.06.27.17.14.26;  author ouster;  state Exp;
  31. branches ;
  32. next     1.1;
  33.  
  34. 1.1
  35. date     88.05.21.11.09.42;  author ouster;  state Exp;
  36. branches ;
  37. next     ;
  38.  
  39. 1.6.1.1
  40. date     91.12.02.21.01.18;  author kupfer;  state Exp;
  41. branches ;
  42. next     ;
  43.  
  44.  
  45. desc
  46. @@
  47.  
  48.  
  49. 1.6
  50. log
  51. @Use function prototypes (except for varargs functions).
  52. @
  53. text
  54. @/*
  55.  * memInt.h --
  56.  *
  57.  *    Defines things that are shared across the procedures that
  58.  *    do dynamic storage allocation (malloc, free, etc) but aren't
  59.  *    visible to users of the storage allocator.
  60.  *
  61.  * Copyright 1988 Regents of the University of California
  62.  * Permission to use, copy, modify, and distribute this
  63.  * software and its documentation for any purpose and without
  64.  * fee is hereby granted, provided that the above copyright
  65.  * notice appear in all copies.  The University of California
  66.  * makes no representations about the suitability of this
  67.  * software for any purpose.  It is provided "as is" without
  68.  * express or implied warranty.
  69.  *
  70.  * $Header: /sprite/src/lib/c/stdlib/RCS/memInt.h,v 1.5 89/08/13 16:27:12 mgbaker Exp Locker: kupfer $ SPRITE (Berkeley)
  71.  */
  72.  
  73. #ifndef _MEMINT
  74. #define _MEMINT
  75.  
  76. #ifndef _SYNCUSER
  77. #include "sync.h"
  78. #endif
  79. #ifndef _STDLIB
  80. #include "stdlib.h"
  81. #endif
  82.  
  83. #include <cfuncproto.h>
  84.  
  85. /*
  86.  * If the MEM_TRACE flag is defined, extra code and data structures will
  87.  * be compiled to allow programs to trace malloc and free calls.
  88. #define MEM_TRACE
  89.  */
  90.  
  91. /*
  92.  * WARNING: several of the macros in this file expect both integers and
  93.  * pointers to be 32 bits (4 bytes) long.
  94.  */
  95.  
  96. /*
  97.  * This storage allocator consists of two independent allocators,
  98.  * one used for binned objects and the other used for large objects.
  99.  * Objects <= SMALL_SIZE are automatically binned, and all objects
  100.  * larger than BIN_SIZE are allocated with the large object
  101.  * allocator.  Objects in between these two sizes are normally
  102.  * allocated with the large allocator, but may be binned by calling
  103.  * Mem_Bin.
  104.  *
  105.  * Both allocators deal with "blocks" of storage, which correspond
  106.  * roughly to the areas that users request and free.  Each block of
  107.  * storage consists of an administrative area (usually a single word)
  108.  * followed by the useable area.  All allocations are done in even
  109.  * numbers of words, which means that clients may occasionally get more
  110.  * bytes than they asked for.  Malloc returns the address of the word
  111.  * just after the administrative area.  The first word of the administrative
  112.  * area is called the administrative word;  it allows us to keep track of
  113.  * which blocks are in use and which are free, and also to keep track of
  114.  * the sizes of blocks so clients don't have to know how large a block is
  115.  * when they free it.  The low-order bit of the administrative word
  116.  * indicates whether or not the block is free.  The next-to-low-order bit
  117.  * of the administrative word is used to indicate that this is a "dummy
  118.  * block":  for blocks on the un-binned list, this means that the block
  119.  * marks an area not belonging to the allocator;  for blocks returned to
  120.  * the "free" procedure, this means that the block must go back to the
  121.  * binned allocator.  The rest of the word tells how large the block is
  122.  * (in bytes including the administrative area).  Using the low-order bits
  123.  * for flags works because all blocks that we allocate are always multiples
  124.  * of 4 bytes in length.  There is one exception to this usage of the
  125.  * administrative word, which occurs for free binned objects.  In this
  126.  * case the word is a link to the next free binned object instead of a
  127.  * size.  If tracing is enabled, then the administrative area also contains
  128.  * a couple of other fields in addition to the administrative word.  The
  129.  * macros below define the format of the administrative area and how to
  130.  * access it.
  131.  */
  132.  
  133. #ifdef MEM_TRACE
  134.  
  135. typedef struct {
  136.     int        admin;        /* Administrative word. */
  137.     Address    pc;        /* PC of call to malloc. */
  138.     int        origSize;    /* Original size given to malloc. */
  139.     int        padding;    /* To make it double word aligned. */
  140. } AdminInfo;
  141.  
  142. #define GET_ADMIN(blockPtr)    (((AdminInfo *) (blockPtr))->admin)
  143. #define SET_ADMIN(blockPtr, value)  \
  144.             ((AdminInfo *) (blockPtr))->admin = (int) (value)
  145.  
  146. #define GET_PC(blockPtr)    (((AdminInfo *) (blockPtr))->pc)
  147. #define SET_PC(blockPtr)    ((AdminInfo *) (blockPtr))->pc = Mem_CallerPC()
  148.  
  149. #define GET_ORIG_SIZE(blockPtr)    (((AdminInfo *) (blockPtr))->origSize)
  150. #define SET_ORIG_SIZE(blockPtr,size)    \
  151.             ((AdminInfo *) (blockPtr))->origSize = size
  152.  
  153. #else
  154.  
  155. typedef double AdminInfo;
  156.  
  157. #define GET_ADMIN(blockPtr)    (*(int *)(AdminInfo *) (blockPtr))
  158. #define SET_ADMIN(blockPtr, value) *((int *)(AdminInfo *) (blockPtr)) = (int) (value)
  159.  
  160. #endif MEM_TRACE
  161.  
  162. #define USE_BIT        1
  163. #define DUMMY_BIT    2
  164. #define FLAG_BITS    3
  165. #define ADMIN_BITS(admin)    ((admin) & FLAG_BITS)
  166. #define IS_IN_USE(admin)    ((admin) & USE_BIT)
  167. #define IS_DUMMY(admin)        (((admin) & FLAG_BITS) == (USE_BIT|DUMMY_BIT))
  168. #define MARK_DUMMY(admin)    ((admin) | (USE_BIT|DUMMY_BIT))
  169. #define MARK_IN_USE(admin)    ((admin) | USE_BIT)
  170. #define MARK_FREE(admin)    ((admin) & ~FLAG_BITS)
  171. #define SIZE(admin)        ((admin) & ~FLAG_BITS)
  172.  
  173. /*
  174.  * The memory manager is a monitor.  The following definition is
  175.  * for its monitor lock.
  176.  */
  177.  
  178. extern Sync_Lock memMonitorLock;
  179. #define LOCKPTR (&memMonitorLock)
  180.  
  181.  
  182. /*
  183.  * ----------------------------------------------------------------------------
  184.  *
  185.  *    Binned-object allocator: it keeps a separate linked free list
  186.  *    for each size of object less than SMALL_SIZE bytes in size and
  187.  *    a free list for all objects less than BIN_SIZE that have been 
  188.  *    specified as being binned by a call to Mem_Bin.  The blocks on
  189.  *    each list are linked together via their administrative words
  190.  *    terminated by a NULL pointer.  Allocation and freeing are done in
  191.  *    a stack-like manner from the front of the free lists.
  192.  *
  193.  *    The following definitions are related:  if you change one, you'll
  194.  *    have to change several:
  195.  *
  196.  *    GRANULARITY: The difference in size between succesive buckets.  This
  197.  *        is determined by data alignment restrictions and should be
  198.  *        a power of 2 to allow for shifting to map from size to bucket.
  199.  *    SIZE_SHIFT: The shift distance to convert between size and bucket.
  200.  *    SMALL_SIZE:        largest blocksize (total including
  201.  *                administrative word) managed by default by
  202.  *                the binned-object allocator.
  203.  *    BIN_SIZE:        largest possible that can be binned.
  204.  *
  205.  *    These can be computed from the above constants.
  206.  *
  207.  *    SMALL_BUCKETS:        number of free lists corresponding to
  208.  *                sizes <= SMALL_SIZE.
  209.  *    BIN_BUCKETS:        total number of binned free lists.
  210.  *    BYTES_TO_BLOCKSIZE:    how many bytes a block must contain (total
  211.  *                including admin. word) to satisfy a user
  212.                 request in bytes.
  213.  *    BLOCKSIZE_TO_INDEX:    which free list to use for blocks of a given
  214.  *                size (total including administrative word).
  215.  *    INDEX_TO_BLOCKSIZE: the (maximum) size corresponding to a bucket.
  216.  *        This will include the size of the administrative word.
  217.  *
  218.  *    This is independent.
  219.  *
  220.  *    BLOCKS_AT_ONCE:        when allocating a new region to hold blocks of
  221.  *                a given size, how many blocks worth should
  222.  *                be allocated at once.
  223.  *
  224.  * ----------------------------------------------------------------------------
  225.  */
  226.  
  227. /*
  228.  * 8 byte granularity to handle SPUR and SPARC.
  229.  */
  230. #define GRANULARITY            8
  231. #define SIZE_SHIFT            3
  232. /*
  233.  * These sizes are optimized towards the kernels memory usage, 1/89.
  234.  */
  235. #define SMALL_SIZE            271
  236. #define    BIN_SIZE            4199
  237.  
  238. #define SMALL_BUCKETS            ((SMALL_SIZE+GRANULARITY-1)/GRANULARITY)
  239. #define BIN_BUCKETS            ((BIN_SIZE+GRANULARITY-1)/GRANULARITY)
  240. #define MASK                (GRANULARITY-1)
  241. #define BYTES_TO_BLOCKSIZE(bytes) ((bytes+MASK+sizeof(AdminInfo)) & (~MASK))
  242. #define BLOCKSIZE_TO_INDEX(size)  ((size)>>SIZE_SHIFT)
  243. #define INDEX_TO_BLOCKSIZE(index) ((index)<<SIZE_SHIFT)
  244.  
  245. #define BLOCKS_AT_ONCE            16
  246.  
  247. /*
  248.  * The following array holds pointers to the first free blocks of each size.
  249.  * Bucket i holds blocks whose total length is 4*i bytes (including the
  250.  * administrative info).  Blocks from bucket i are used to satisfy user
  251.  * requests ranging from (4*i)-sizeof(AdminInfo) bytes up to (4*i)-1 bytes.  
  252.  * Buckets 0 and 1 are never used, since they correspond to blocks too small
  253.  * to hold any information for the user.  If the list head is NOBIN, it
  254.  * means that this size isn't binned:  use the large block allocator.
  255.  */
  256.  
  257. extern Address    memFreeLists[BIN_BUCKETS];
  258. #define NOBIN    ((Address) -1)
  259.  
  260. /*
  261.  * Used to gather statistics about allocations:
  262.  */
  263.  
  264. extern int mem_NumBlocks[];        /* Total number of existing blocks,
  265.                      * both allocated and free, for each
  266.                      * small size.  */
  267. extern int mem_NumBinnedAllocs[];    /* Total number of allocation requests
  268.                      * made for blocks of each small size.
  269.                      */
  270.  
  271. /*
  272.  * ----------------------------------------------------------------------------
  273.  *    Large-object allocator:  used for blocks that aren't binned.
  274.  *    There should be relatively few allocations made by the
  275.  *    large-object allocator.  Since all the blocks it allocates are
  276.  *    relatively large, fragmentation should be less than it would be
  277.  *    if it allocated small blocks too. All of the blocks, in use or
  278.  *    not, are kept in a single linked list using their administrative
  279.  *    words.  The address of the next block in the list is found by
  280.  *    adding the size of the current block to the address of its
  281.  *    administrative word.  Things are complicated slightly because the
  282.  *    storage area managed by this allocator may be discontiguous:  there
  283.  *    could be several large regions that it manages, separated by gaps
  284.  *    that are managed by some other storage allocator (e.g. the
  285.  *    binned-object allocator).  In this case, the gaps between regions
  286.  *    are handled by making the gaps look like allocated blocks, with an
  287.  *    administrative word at the end of one region that causes a skip to
  288.  *    the beginning of the next region.  These blocks are called "dummy
  289.  *    blocks", and have special flag bits in their administrative words.
  290.  *    All the blocks within a region are linked together in increasing
  291.  *    order of address.  However, the different regions may appear in any
  292.  *    order on the list.
  293.  * ----------------------------------------------------------------------------
  294.  */
  295.  
  296. extern Address memFirst;        /* Pointer to first block of memory
  297.                      * in the un-binned pool. */
  298. extern Address memLast;            /* Points to dummy block at the end
  299.                      * of the memory list, which always
  300.                      * has zero size. */
  301. extern Address memCurrentPtr;        /* Next block to consider allocating.
  302.                      * Rotates circularly through free
  303.                      * list. */
  304. extern int memLargestFree;        /* This holds the size of the largest
  305.                      * free block that's been seen on the
  306.                      * free list.  It's updated as the
  307.                      * list is traversed.  */
  308. extern int memBytesFreed;        /* Sum of unbinned bytes freed since
  309.                      * the last time we started scanning
  310.                      * the memory list. */
  311.  
  312. /*
  313.  * Minimum size of new regions requested by large-object allocator
  314.  * when storage runs out:
  315.  */
  316.  
  317. #define MIN_REGION_SIZE 2048
  318.  
  319. /*
  320.  * Various stats about large-block allocator:  some are only kept when
  321.  * tracing is enabled.
  322.  */
  323.  
  324. extern int mem_NumLargeBytes;    /* Total amount of storage managed by
  325.                  * the large allocator.  */
  326. extern int mem_NumLargeAllocs;    /* Total number of allocation requests
  327.                  * handled by the large allocator.  */
  328. extern int mem_NumLargeLoops;    /* Number of iterations through the
  329.                  * inner block-checking loop of the
  330.                  * large allocator.  */
  331.  
  332. /*
  333.  * ----------------------------------------------------------------------------
  334.  *    Miscellaneous declarations.
  335.  * ----------------------------------------------------------------------------
  336.  */
  337.  
  338. /*
  339.  * Statistics about total calls to malloc and free.
  340.  */
  341.  
  342. extern int    mem_NumAllocs;
  343. extern int    mem_NumFrees;
  344.  
  345. /*
  346.  * Flag to make sure MemInit gets called once.
  347.  */
  348.  
  349. extern int    memInitialized;
  350.  
  351. /*
  352.  * If tracing is enabled, then when malloc or free is called a
  353.  * trace record will be printed and/or the number of blocks being used
  354.  * by the caller will be stored in the trace array if the block size is
  355.  * in sizeTraceArray. The array is defined with Mem_SetTraceSizes().
  356.  * PrintTrace calls a default printing routine; it can be changed with
  357.  * Mem_SetPrintProc().
  358.  */
  359. #define MAX_NUM_TRACE_SIZES    8
  360. #define    MAX_CALLERS_TO_TRACE    16
  361. typedef struct {
  362.     Mem_TraceInfo    traceInfo;
  363.     struct {
  364.     Address    callerPC;
  365.     int    numBlocks;
  366.     } allocInfo[MAX_CALLERS_TO_TRACE];
  367. } MemTraceElement;
  368.  
  369. extern MemTraceElement    memTraceArray[];
  370. extern    int        memNumSizesToTrace;
  371.  
  372. /*
  373.  * Routine to do printing for tracing and status printing.  Can be
  374.  * reset with Mem_SetPrintProc.
  375.  */
  376.  
  377. extern int        (*memPrintProc)(); /* e.g., fprintf */
  378. extern ClientData    memPrintData;
  379.  
  380. /*
  381.  * Can free storage be freed a second time?
  382.  */
  383.  
  384. extern int        memAllowFreeingFree;
  385.  
  386. /*
  387.  * Various procedures used internally by the allocator.
  388.  */
  389.  
  390. #ifdef KERNEL
  391. extern Address    MemChunkAlloc _ARGS_((int size, Address *addressPtr));
  392. #else
  393. extern Address    MemChunkAlloc _ARGS_((int size));
  394. #endif
  395.  
  396. extern void    MemDoTrace _ARGS_((Boolean allocated, Address infoPtr,
  397.                    Address curPC, int size));
  398. extern void    MemInit _ARGS_((void));
  399.  
  400. #endif _MEMINT
  401. @
  402.  
  403.  
  404. 1.6.1.1
  405. log
  406. @Initial branch for Sprite server.
  407. @
  408. text
  409. @d17 1
  410. a17 1
  411.  * $Header: /sprite/src/lib/c/stdlib/RCS/memInt.h,v 1.6 90/10/11 22:12:06 kupfer Exp $ SPRITE (Berkeley)
  412. @
  413.  
  414.  
  415. 1.5
  416. log
  417. @The returned addresses for small allocations now fall on double-word
  418. boundaries so that store and load double instructions for the sun4 will
  419. work.
  420. @
  421. text
  422. @d17 1
  423. a17 1
  424.  * $Header: /sprite/src/lib/c/stdlib/RCS/memInt.h,v 1.4 89/01/30 15:38:46 brent Exp Locker: mgbaker $ SPRITE (Berkeley)
  425. d30 2
  426. d324 1
  427. a324 1
  428. extern int        (*memPrintProc)();
  429. d337 9
  430. a345 3
  431. extern Address        MemChunkAlloc();
  432. extern void        MemDoTrace();
  433. extern void        MemInit();
  434. @
  435.  
  436.  
  437. 1.4
  438. log
  439. @Fixed configuration constants so they depend on a granularity,
  440. i.e. 4 bytes or 8 bytes.  Set to 8 to support SPUR, SPARC
  441. @
  442. text
  443. @d17 1
  444. a17 1
  445.  * $Header: memInt.h,v 1.3 88/08/20 21:08:50 ouster Exp $ SPRITE (Berkeley)
  446. d84 1
  447. d100 1
  448. a100 1
  449. typedef int AdminInfo;
  450. d102 2
  451. a103 2
  452. #define GET_ADMIN(blockPtr)    (*((AdminInfo *) (blockPtr)))
  453. #define SET_ADMIN(blockPtr, value) *((AdminInfo *) (blockPtr)) = (int) (value)
  454. @
  455.  
  456.  
  457. 1.3
  458. log
  459. @Add declarations for mem_NumAllocs, mem_NumFrees, clean up typos.
  460. @
  461. text
  462. @d17 1
  463. a17 1
  464.  * $Header: memInt.h,v 1.2 88/06/27 17:14:26 ouster Exp $ SPRITE (Berkeley)
  465. d137 2
  466. a138 2
  467.  *    Definitions (these are all related:  if you change one, you'll
  468.  *    have to change several):
  469. d140 4
  470. d147 4
  471. a152 1
  472.  *    BIN_SIZE:        largest possible that can be binned.
  473. d159 5
  474. d171 9
  475. a179 2
  476. #define SMALL_SIZE            127
  477. #define SMALL_BUCKETS            ((SMALL_SIZE+3)/4)
  478. d181 8
  479. a188 3
  480. #define BIN_BUCKETS            ((BIN_SIZE+3)/4)
  481. #define BYTES_TO_BLOCKSIZE(bytes)    ((bytes+3+sizeof(AdminInfo)) & (~3))
  482. #define BLOCKSIZE_TO_INDEX(size)    ((size)>>2)
  483. @
  484.  
  485.  
  486. 1.2
  487. log
  488. @Don't use syncMonitor.h anymore.
  489. @
  490. text
  491. @d17 1
  492. a17 1
  493.  * $Header: memInt.h,v 1.1 88/05/21 11:09:42 ouster Exp $ SPRITE (Berkeley)
  494. d32 1
  495. a32 1
  496.  * be compiled to allow programs to trace Mem_Alloc and Mem_Free calls.
  497. d55 1
  498. a55 1
  499.  * bytes than they asked for.  Mem_Alloc returns the address of the word
  500. d82 2
  501. a83 2
  502.     Address    pc;        /* PC of call to Mem_Alloc. */
  503.     int        origSize;    /* Original size given to Mem_Alloc. */
  504. d259 7
  505. d272 1
  506. a272 1
  507.  * If tracing is enabled, then when Mem_Alloc or Mem_Free is called a
  508. @
  509.  
  510.  
  511. 1.1
  512. log
  513. @Initial revision
  514. @
  515. text
  516. @d17 1
  517. a17 1
  518.  * $Header: proto.h,v 1.2 88/03/11 08:39:40 ouster Exp $ SPRITE (Berkeley)
  519. d23 2
  520. a24 2
  521. #ifndef _SYNCMONITOR
  522. #include "syncMonitor.h"
  523. @
  524.